package leetcode_41_60;

public class maxSubArray_53 {
    /**
     * 找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
     * 子数组 是数组中的一个连续部分。
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        /*
        找到以每个数字结尾的连续子数组的最大和是多少
        向后遍历
         */
        int[] lastMax =new int[nums.length];  //以每个数字结尾的连续子数组的最大和
        lastMax[0]=nums[0];
        int ans=lastMax[0];
        for(int i=1;i<nums.length;i++) {
            if (lastMax[i - 1] < 0) //如果之前的最大和小于等于0，并且小于当前值，直接切断，从当前开始
                lastMax[i] = nums[i];
            else
                lastMax[i] = lastMax[i - 1] + nums[i];
            if (ans < lastMax[i])
                ans = lastMax[i];
        }
        return ans;
    }
}
